package 数据结构和算法.算法.排序算法.插入排序;

import java.util.Arrays;

/**
 * 插入排序，一般也被称为直接插入排序。对于少量元素的排序，
 * 它是一个有效的算法 [1]  。插入排序是一种最简单的排序方法，
 * 它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表
 */
public class InsertionSort {
    public static void main(String[] args) {
        int[] array = {2, 5, 1, 3, 0};
        sort(array);
        System.out.printf(Arrays.toString(array));

    }

    public static void sort(int[] array) {
        for (int i = 1; i < array.length; ++i) {
            int temp = array[i];
            int j = i - 1;
            while (j >= 0 && array[j] > temp) {
                array[j + 1] = array[j];
                j--;
            }

            array[j + 1] = temp;
        }
    }
}
